// class Point {
//     constructor(x: number, y: number, z: number) { }
// }

// class Node {
//     constructor(point: Point, left: Node | null = null, right: Node | null = null) { }
// }

// class KDTree {
//     private root: Node | null = null;

//     build(points: Point[]): void {
//         this.root = this.buildTree(points, 0);
//     }

//     private buildTree(points: Point[], depth: number): Node | null {
//         if (points.length === 0) {
//             return null;
//         }

//         const axis = depth % 3;
//         points.sort((a, b) => this.comparePoints(a, b, axis));

//         const medianIndex = Math.floor(points.length / 2);
//         const medianPoint = points[medianIndex];

//         const leftPoints = points.slice(0, medianIndex);
//         const rightPoints = points.slice(medianIndex + 1);

//         const left = this.buildTree(leftPoints, depth + 1);
//         const right = this.buildTree(rightPoints, depth + 1);

//         return new Node(medianPoint, left, right);
//     }

//     private comparePoints(a: Point, b: Point, axis: number): number {
//         if (axis === 0) {
//             return a.x - b.x;
//         } else if (axis === 1) {
//             return a.y - b.y;
//         } else {
//             return a.z - b.z;
//         }
//     }

//     nearestNeighbor(target: Point): Point | null {
//         let bestPoint: Point | null = null;
//         let bestDistance = Infinity;

//         this.searchNearest(this.root, target, 0);

//         return bestPoint;

//         function distanceSquared(a: Point, b: Point): number {
//             const dx = a.x - b.x;
//             const dy = a.y - b.y;
//             const dz = a.z - b.z;
//             return dx * dx + dy * dy + dz * dz;
//         }

//         function searchNearest(node: Node | null, target: Point, depth: number) {
//             if (node === null) {
//                 return;
//             }

//             const axis = depth % 3;
//             const currentPoint = node.point;

//             const currentDistance = distanceSquared(currentPoint, target);
//             if (currentDistance < bestDistance) {
//                 bestPoint = currentPoint;
//                 bestDistance = currentDistance;
//             }

//             const compareValue = target[axis] - currentPoint[axis];

//             let nearNode: Node | null;
//             let farNode: Node | null;

//             if (compareValue < 0) {
//                 nearNode = node.left;
//                 farNode = node.right;
//             } else {
//                 nearNode = node.right;
//                 farNode = node.left;
//             }

//             searchNearest(nearNode, target, depth + 1);

//             if (Math.abs(compareValue) < bestDistance) {
//                 searchNearest(farNode, target, depth + 1);
//             }
//         }
//     }
// }

// // Usage example:
// const points: Point[] = [
//     new Point(2, 3, 4),
//     new Point(5, 7, 1),
//     new Point(9, 2, 8),
//     new Point(6, 4, 3),
//     new Point(1, 8, 5),
//     new Point(7, 9, 2)
// ];

// const kdtree = new KDTree();
// kdtree.build(points);

// const targetPoint = new Point(3, 6, 2
